package top100.binarysearch;

import top100.twopointer.Solution287;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/26 12:31
 * @description:
 */
public class Solution74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0, right = matrix.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[mid][0] > target) {
                right = mid - 1;
            } else if (matrix[mid][0] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        int row = right;
        if (!(row >= 0 && row < matrix.length)) {
            return false;
        }
        left = 0;
        right = matrix[0].length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[row][mid] > target) {
                right = mid - 1;
            } else if (matrix[row][mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution74 solution = new Solution74();
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        System.out.println(solution.searchMatrix(matrix, 3));

        System.out.println(solution.searchMatrix(matrix, 13));

        System.out.println(solution.searchMatrix(new int[][]{{1}}, 1));

        System.out.println(solution.searchMatrix(new int[][]{{1}}, 0));

        System.out.println(solution.searchMatrix(new int[][]{{1,3}}, 3));

    }
}
